module share.container;

import core.sync.mutex, std.algorithm;
import std.c.string : memcpy, memmove, memset;

const QUEUE_MAX = 100;


const SUnbalancedOperation = "Unbalanced stack or queue operation";
const SArgumentOutOfRange = "Argument out of range";


// Queue implemented over array, using wrapping.
public struct Queue(T)
{
    private int _head = 0;
    private int _tail = 0;
    private int _count = 0;
    private int _capacity = 0;
    private T[] _payload = null;
    
    
    private void grow()
    {
        int newCap;

        newCap = _capacity * 2;
        if (newCap == 0)
            newCap = 4;
        else if (newCap < 0)
            throw new Exception("OutOfMemoryError");
        SetCapacity(newCap);
    }
    
    private void SetCapacity(int cap)
    {
        int tailCount, offset;

        offset = cap - _capacity;
        if (offset == 0)
            return;
  
        // If head <= tail, then part of the queue wraps around
        // the end of the array; don't introduce a gap in the queue.
        if ((_head < _tail) || ((_head == _tail) && (_count > 0)))
            tailCount = _capacity - _tail;
        else
            tailCount = 0;
  
        if (offset > 0)
        {
            _capacity = cap;
            _payload.length = _capacity;
        }
        if (tailCount > 0)
        {
            memmove(_payload.ptr+(_tail + offset), _payload.ptr+_tail, tailCount * T.sizeof);
            if (offset > 0)
                memset(_payload.ptr+_tail, 0, offset * T.sizeof);
            else if (offset < 0)
                memset(_payload.ptr+_count, 0, (- offset) * T.sizeof);
            _tail += offset;
        }
        else if (_tail > 0)
        {
            if (_count > 0)
            {
                memmove(_payload.ptr, _payload.ptr+_tail, _count * T.sizeof);
                memset(_payload.ptr+_count, 0, _tail * T.sizeof);
            }
            _head -= _tail;
            _tail = 0;
        }
        if (offset < 0)
        {
            _capacity = cap;
            _payload.length = _capacity;
        }
    }
    
    private void DoSetCapacity(int cap)
    {
        if (cap < _count)
            throw new Exception(SArgumentOutOfRange);
        SetCapacity(cap);
    }
    
    private int GetCapacity()
    {
        return _capacity;
    }
    
    public this(int capacity)
    {
        if (capacity < 0)
            throw new Exception(SArgumentOutOfRange);

        this._head = 0;
        this._tail = 0;
        this._count = 0;
        this._capacity = capacity;
        this._payload = new T[capacity];
    }

    public ~this()
    {
        clear();
    }
    
    public bool contains(in T item)
    {
        int index = this._tail;
        int qcount = this._count;

        while (qcount-- > 0)
        {
            if (item is T.init)
            {
                if (this._payload[index] is T.init)
                {
                    return true;
                }
            }
            else
            {
                if (this._payload[index] !is T.init && (this._payload[index] is item))
                {
                    return true;
                }
            }
            index = (index + 1) % this._capacity;
        }
        return false;
    }
    
    public void enqueue(T value)
    {
        if (_count == _capacity)
            grow();
        _payload[_head] = value;
        _head = (_head + 1) % _capacity;
        _count++;
    }
    
    public T dequeue()
    {
        if (_count == 0)
            throw new Exception(SUnbalancedOperation);
        T result = _payload[_tail];
        _payload[_tail] = T.init;
        _tail = (_tail + 1) % _capacity;
        _count--;
        return result;
    }
    
    public T peek()
    {
        if (_count == 0)
            throw new Exception(SUnbalancedOperation);
        return _payload[_tail];
    }
    
    public void clear()
    {
        while (_count > 0)
            dequeue();
        _head = 0;
        _tail = 0;
        _count = 0;
        _capacity = 0;
    }
    
    public void trimExcess()
    {
        SetCapacity(_count);
    }
    
    @property const nothrow public int count() { return _count; }
    @property public int capacity() { return GetCapacity(); }
    @property public void capacity(int value) { DoSetCapacity(value); }
    @property const nothrow public bool empty() { return _count == 0; }
}

unittest
{
    // Test Enqueue
    Queue!int q;
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    
    assert(q.count() == 3, "Queue Enqueue count wrong");
}

unittest
{
    // Test Dequeue
    Queue!int q;
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    
    while (q.count() > 1)
        q.dequeue();
    
    assert(q.count() == 1, "Queue Dequeue count wrong");
}

unittest
{
    // Test clear
    Queue!int q;
    q.enqueue(1);
    q.enqueue(2);
    
    q.clear();
    
    assert(q.count() == 0, "Queue clear count wrong");
}

unittest
{
    // Test Trim
    Queue!int q;
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    q.enqueue(4);
    q.enqueue(5);
    
    q.trimExcess();
    
    assert(q.capacity() == q.count(), "Queue capacity wrong");
}

unittest
{
    // Test contains
    Queue!int q;
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    q.enqueue(4);
    q.enqueue(5);
    
    assert(q.contains(3), "Queue contains wrong");
    assert(q.contains(10) == false, "Queue contains wrong");
}



public struct Stack(T)
{
    private int _count = 0;
    private int _capacity = 0;
    private T[] _payload = null;

    private void grow()
    {
        int newCap;

        newCap = _capacity * 2;
        if (newCap == 0)
            newCap = 4;
        else if (newCap < 0)
            throw new Exception("OutOfMemoryError");
        SetCapacity(newCap);
    }
    
    private void SetCapacity(int cap)
    {
        if (cap < _count)
            throw new Exception(SArgumentOutOfRange);
        _capacity = cap;
        _payload.length = cap;
    }
    
    private int GetCapacity()
    {
        return _capacity;
    }
    
    public this(int capacity)
    {
        if (capacity < 0)
            throw new Exception(SArgumentOutOfRange);

        this._count = 0;
        this._capacity = capacity;
        this._payload = new T[capacity];
    }

    public ~this()
    {
        clear();
    }
    
    public void clear()
    {
        while (_count > 0)
            pop();
        SetCapacity(0);
    }
    
    public void push(T value)
    {
        if (_count == _capacity)
            grow();
        _payload[_count] = value;
        _count++;
    }
    
    public T pop()
    {
        if (_count == 0)
            throw new Exception(SUnbalancedOperation);
        _count--;
        T result = _payload[_count];
        _payload[_count] = T.init;
        return result;
    }
    
    public T peek()
    {
        if (_count == 0)
            throw new Exception(SUnbalancedOperation);
        return _payload[_count - 1];
    }
    
    public void trimExcess()
    {
        SetCapacity(_count);
    }

    @property const nothrow public int count() { return _count; }
    @property public int capacity() { return GetCapacity(); }
    @property public void capacity(int value) { SetCapacity(value); }
    @property const nothrow public bool empty() { return _count == 0; }
}

/*public class Queue(T)
{
    protected size_t m_btCount;

    protected size_t m_btQPushPos;
    protected size_t m_btQPopPos;
    
    protected T[QUEUE_MAX] m_lpCircularQ;

    protected Mutex m_cs;

    public this()
    {
        m_cs = new Mutex;

        m_btQPushPos = 0;
        m_btQPopPos = 0; 

        m_btCount = 0;
    }
    
    public ~this()
    {
        destroy(m_cs);
    }
    
    public bool pushQ(T lpbtQ)
    {
        bool fRet = true;

        m_cs.lock();
        scope(exit) m_cs.unlock();

        if (m_btQPushPos + 1 == m_btQPopPos || (m_btQPushPos + 1 == QUEUE_MAX && !m_btQPopPos))
            return false; // Queue is full.

        m_lpCircularQ[m_btQPushPos] = lpbtQ;
        m_btQPushPos++;
        m_btCount++;

        if (m_btQPushPos == QUEUE_MAX)
            m_btQPushPos = 0;
        
        return true;
    }
    
    public T popQ()
    {
        m_cs.lock();
        scope(exit) m_cs.unlock();
        
        if (m_btQPopPos == QUEUE_MAX)
            m_btQPopPos = 0;

        if (m_btQPopPos == m_btQPushPos)
            return T.init;            // No event.

        m_btQPopPos++;
        m_btCount--;

        return m_lpCircularQ[m_btQPopPos - 1];
    }
    
    public T peekQ()
    {
        m_cs.lock();
        scope(exit) m_cs.unlock();
        
        size_t peekPos = m_btQPopPos;
        
        if (peekPos == QUEUE_MAX)
            peekPos = 0;

        if (peekPos == m_btQPushPos)
            return T.init;            // No event.

        return m_lpCircularQ[peekPos];
    }
    
    @property const nothrow public uint getCurPushPos() { return m_btQPushPos; }
    @property const nothrow public uint getCurPopPos() { return m_btQPopPos; }
    @property const nothrow public uint count() { return m_btCount; }
    @property const nothrow public bool empty() { return m_btCount == 0; }
}*/


public struct Vector(T)
{
    private T[] _payload = null;
    private int _count = 0;
    private int _capacity = 0;
    //FComparer: IComparer<T>;
    //FOnNotify: TCollectionNotifyEvent<T>;

    private int getCapacity()
    {
        return _capacity;
    }
    
    private void setCapacity(int cap)
    {
        if (cap < _count)
            _count = cap;
        _capacity = cap;
        _payload.length = cap;
    }
    
    private void SetCount(int ACount)
    {
        if (ACount < 0)
            throw new Exception(SArgumentOutOfRange);
        if (ACount > _capacity)
            setCapacity(ACount);
        if (ACount < _count)
            deleteRange(ACount, _count - ACount);
        _count = ACount;
    }
    
    private T GetItem(int Index)
    {
        if ((Index < 0) || (Index >= _count))
            throw new Exception(SArgumentOutOfRange);
        return _payload[Index];
    }
    
    private void SetItem(int Index, T Value)
    {
        if ((Index < 0) || (Index >= _count))
            throw new Exception(SArgumentOutOfRange);

        _payload[Index] = Value;
    }
    
    private void Grow(int ACount)
    {
        int newCount;

        newCount = _capacity;
        if (newCount == 0)
            newCount = ACount;
        else
        {
            do
            {
                newCount = newCount * 2;
                if (newCount < 0)
                    throw new Exception("OutOfMemoryError");
            } while (newCount < ACount);
        }
        setCapacity(newCount);
        
        // Mono
        /*if (_capacity < ACount)
        {
            int num = (_capacity == 0) ? 4 : (_capacity * 2);
            if (num < ACount)
                num = ACount;
            setCapacity(num);
        }*/
    }
    
    private void GrowCheck(int ACount)
    {
        if (ACount > _capacity)
            Grow(ACount);
        else if (ACount < 0)
            throw new Exception("OutOfMemoryError");
    }
    


    //constructor Create; overload;
    //constructor Create(const AComparer: IComparer<T>); overload;
    //constructor Create(Collection: TEnumerable<T>); overload;
    
    public ~this()
    {
        setCapacity(0);
    }
    
    public int add(T Value)
    {
        GrowCheck(_count + 1);
        int index = _count;
        _payload[_count] = Value;
        _count++;
        return index;
    }
    
    public void addRange(T[] Values)
    {
        insertRange(_count, Values);
    }
    
    public int addFirst(T value)
    {
        int index = _count;
        insertAt(0, value);
        return index;
    }
    
    public alias add addLast;
    
    //public void AddRange(const Collection: IEnumerable<T>); overload;
    //public void AddRange(Collection: TEnumerable<T>); overload;
    
    public void insertAt(int Index, T value)
    {
        if ((Index < 0) || (Index > _count))
            throw new Exception(SArgumentOutOfRange);

        GrowCheck(_count + 1);
        if (Index != _count)
        {
            memmove(_payload.ptr+(Index + 1), _payload.ptr+Index, (_count - Index) * T.sizeof);
            memset(_payload.ptr+Index, 0, T.sizeof);
        }
        _payload[Index] = value;
        _count++;
    }
    
    public void insertRange(int Index, T[] arrItems)
    {
        int i;
        if ((Index < 0) || (Index > _count))
            throw new Exception(SArgumentOutOfRange);

        GrowCheck(_count + arrItems.length);
        if (Index != _count)
        {
            memmove(_payload.ptr+(Index + arrItems.length), _payload.ptr+Index, (_count - Index) * T.sizeof);
            memset(_payload.ptr+Index, 0, arrItems.length * T.sizeof);
        }

        for (i = 0; i < arrItems.length; i++)
            _payload[Index + i] = arrItems[i];

        _count += arrItems.length;
    }
    
    //public void InsertRange(int Index: Integer; const Collection: IEnumerable<T>); overload;
    //public void InsertRange(int Index: Integer; const Collection: TEnumerable<T>); overload;
    
    public int remove(T Value)
    {
        int index = indexOf(Value);
        if (index >= 0)
            deleteAt(index);
        return index;
    }
    
    public void deleteAt(int Index)
    {
        if ((Index < 0) || (Index >= _count))
            throw new Exception(SArgumentOutOfRange);
        T oldItem = _payload[Index];
        _payload[Index] = T.init;
        _count--;
        if (Index != _count)
        {
            memmove(_payload.ptr+Index, _payload.ptr+(Index + 1), (_count - Index) * T.sizeof);
            memset(_payload.ptr+_count, 0, T.sizeof);
        }
    }
    
    public void deleteRange(int AIndex, int ACount)
    {
        T[] oldItems;
        int tailCount, i;

        if (ACount == 0)
            return;
        
        if ((AIndex < 0) || (ACount < 0) || (AIndex + ACount > _count)
            || (AIndex + ACount < 0))
            throw new Exception(SArgumentOutOfRange);
        
        oldItems.length = ACount;
        memmove(oldItems.ptr, _payload.ptr+AIndex, ACount * T.sizeof);

        tailCount = _count - (AIndex + ACount);
        if (tailCount > 0)
        {
            memmove(_payload.ptr+AIndex, _payload.ptr+(AIndex + ACount), tailCount * T.sizeof);
            memset(_payload.ptr+(_count - ACount), 0, ACount * T.sizeof);
        }
        else
        {
            memset(_payload.ptr+AIndex, 0, ACount * T.sizeof);
        }
        _count -= ACount;
    }
    
    public T extract(T Value)
    {
        int index = indexOf(Value);
        T result;
        if (index < 0)
            result = T.init;
        else
        {
            result = _payload[index];
            deleteAt(index);
        }
        
        return result;
    }

    public void exchange(int Index1, int Index2)
    {
        std.algorithm.swap(_payload[Index1], _payload[Index2]);
        T temp = _payload[Index1];
        _payload[Index1] = _payload[Index2];
        _payload[Index2] = temp;
    }
    
    public void move(int CurIndex, int NewIndex)
    {
        if (CurIndex == NewIndex)
            return;
        if ((NewIndex < 0) || (NewIndex >= _count))
            throw new Exception(SArgumentOutOfRange);

        T oldItem = _payload[CurIndex];
        _payload[CurIndex] = T.init;
        if (CurIndex < NewIndex)
            memmove(_payload.ptr+CurIndex, _payload.ptr+(CurIndex + 1), (NewIndex - CurIndex) * T.sizeof);
        else
            memmove(_payload.ptr+(NewIndex + 1), _payload.ptr+NewIndex, (CurIndex - NewIndex) * T.sizeof);

        memset(_payload.ptr+NewIndex, 0, T.sizeof);
        _payload[NewIndex] = oldItem;
    }

    public T first()
    {
        return _payload[0];
    }
    
    public T last()
    {
        return _payload[_count - 1];
    }
    
    public void clear()
    {
        _count = 0;
        setCapacity(0);
    }

    public bool contains(T Value)
    {
        return indexOf(Value) >= 0;
    }
    
    public int indexOf(T Value)
    {
        int index;

        for (index = 0; index < _count; index++)
            if (_payload[index] is Value)
                return index;
        return -1;
    }
    
    public int lastIndexOf(T Value)
    {
        int index;

        for (index = _count-1; index >= 0; index--)
            if (_payload[index] is Value)
                return index;
        return -1;
    }
    
    public void reverse(int AIndex, int ACount)
    {
        if ((AIndex < 0) || (ACount < 0) || (_count - AIndex < ACount))
            throw new Exception(SArgumentOutOfRange);

        T tmp;

        int start = AIndex;
        int end = ACount - 1;
        while (start < end)
        {
            //std.algorithm.swap(_payload[start], _payload[end]);
            tmp = _payload[start];
            _payload[start] = _payload[end];
            _payload[end] = tmp;
            start++;
            end--;
        }
    }
    
    public void reverse()
    {
        reverse(0, _count);
    }

    //public void Sort; overload;
    //public void Sort(const AComparer: IComparer<T>); overload;
    //function BinarySearch(const Item: T; out Index: Integer): Boolean; overload;
    //function BinarySearch(const Item: T; out Index: Integer; const AComparer: IComparer<T>): Boolean; overload;

    public void trimExcess()
    {
        setCapacity(_count);
    }
        

    //function ToArray: TArray<T>; override; final;
        
    public int opApply (int delegate(ref int index, ref T value) dg)
    {
        int result = 0, n = 0;
        while (true)
        {
            if (n >= _count) break;
            result = dg (n, _payload[n]);
            if (result != 0) break;
            n++;
        }
        return result;
    }
    
    public int opApply (int delegate(ref T value) dg)
    {
        int result = 0, n = 0;
        while (true)
        {
            if (n >= _count) break;
            result = dg (_payload[n]);
            if (result != 0) break;
            n++;
        }
        return result;
    }

    @property const nothrow public int count() { return _count; }
    @property void count(int value) { SetCount(value); }
    @property public int capacity() { return getCapacity(); }
    @property public void capacity(int value) { setCapacity(value); }
    @property const nothrow public bool empty() { return _count == 0; }
    
    public T opIndex (int index)
    {
        return GetItem(index);
    }
    
    public void opIndexAssign (ref T value, int index)
    {
        SetItem(index, value);
    }
}

unittest
{
    // Test add
    Vector!int list;
    list.add(1);
    list.add(2);
    list.add(3);
    
    assert(list.count() == 3, "Vector Add wrong count");
}

unittest
{
    // Test AddRange
    Vector!int list;
    list.addRange([1, 2, 3]);
    
    assert(list.count() == 3, "Vector AddRange wrong count");
}

unittest
{
    // Test Insert
    Vector!int list;
    list.addRange([1, 2, 3]);
    
    list.insertAt(1, 99);
    assert(list[1] == 99, "Vector Insert wrong 1");
    
    list.insertAt(0, 50);
    assert(list[0] == 50, "Vector Insert wrong 2");
    
    list.insertAt(list.count(), 100);
    assert(list[list.count()-1] == 100, "Vector Insert wrong 3");
}

unittest
{
    // Test Insert
    Vector!int list;
    list.insertAt(0, 99);
    
    assert(list[0] == 99, "Vector Insert wrong");
}

unittest
{
    // Test Insert
    Vector!int list;
    list.addRange([1, 2, 3]);
    list.insertRange(0, [4, 5, 6]);
    
    assert(list[0] == 4, "Vector InsertRange wrong 1");
    assert(list[1] == 5, "Vector InsertRange wrong 2");
    assert(list[2] == 6, "Vector InsertRange wrong 3");
}

unittest
{
    // Test Clear
    Vector!int list;
    list.addRange([1, 2, 3]);
    list.clear();
    
    assert(list.count() == 0, "Vector Clear wrong count");
}

unittest
{
    // Test Delete
    Vector!int list;
    list.addRange([1, 2, 3]);
    list.deleteAt(1);
    
    assert(list.count() == 2, "Vector AddRange wrong count");
    assert(list.first() == 1, "Vector First wrong");
    assert(list.last() == 3, "Vector Last wrong");
}

unittest
{
    // Test Remove
    Vector!int list;
    list.addRange([100, 500, 300]);
    list.remove(500);
    
    assert(list.count() == 2, "Vector Remove wrong count");
    assert(list.first() == 100, "Vector First wrong");
    assert(list.last() == 300, "Vector Last wrong");
}

unittest
{
    // Test DeleteRange
    Vector!int list;
    list.addRange([1, 2, 3, 4, 5, 6]);
    list.deleteRange(1, 4);
    
    assert(list.count() == 2, "Vector DeleteRange wrong count");
    assert(list.first() == 1, "Vector First wrong");
    assert(list.last() == 6, "Vector Last wrong");
}

unittest
{
    // Test Reverse
    Vector!int list;
    list.addRange([1, 2, 3]);
    
    list.reverse();
    
    assert(list[0] == 3, "Vector Reverse wrong");
    assert(list[2] == 1, "Vector Reverse wrong");
}

unittest
{
    // Test First, Last
    Vector!int list;
    list.addRange([1, 2, 3]);
    
    assert(list.first() == 1, "Vector First wrong");
    assert(list.last() == 3, "Vector Last wrong");
}

unittest
{
    // Test Contains
    Vector!int list;
    list.addRange([1, 2, 3]);
    
    bool found1 = list.contains(2);
    bool found2 = list.contains(5);
    
    assert(found1 == true, "Vector Contains wrong(found1)");
    assert(found2 == false, "Vector Contains wrong(found2)");
}

unittest
{
    // Test IndexOf, LastIndexOf
    Vector!int list;
    list.addRange([1, 2, 3, 4, 5, 5, 6]);
    
    int index1 = list.indexOf(5);
    int index2 = list.lastIndexOf(5);
    
    assert(index1 == 4, "Vector IndexOf wrong");
    assert(index2 == 5, "Vector LastIndexOf wrong");
}

unittest
{
    // Test TrimExcess
    Vector!int list;
    list.setCapacity(50);
    
    assert(list.count() != list.capacity(), "Vector capacity wrong");
    
    list.trimExcess();
    
    assert(list.count() == list.capacity(), "Vector capacity wrong");
}